package com.zh.note.huawei.twohundred.最少数量线段覆盖or区间交叠问题;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author: zhanghuan
 * @date: 2023/8/9 10:40
 * @description: create it
 */
public class Main {
    /**
     * 将区间内的点全部加入的map中，map的key是横坐标，value是出现次数
     * 遍历区间，如果map中有区间内的值，只出现一次则跳过，区间内的值，出现都不止一次，则区间内的值出现次数全部减1
     * n-删除次数 即为选择的区间数
     *
     * @param args
     */
    public static void main(String[] args) {
        // Scanner sc = new Scanner(System.in);
        // int n = sc.nextInt();
        // int[][] points = new int[n][2];
        // for (int i = 0; i < n; i++) {
        //     String[] split = sc.nextLine().split(",");
        //     points[i] = new int[]{Integer.parseInt(split[0], Integer.parseInt(split[1]))};
        // }
        int n = 3;
        int[][] points = {{1, 4}, {2, 5}, {3, 6}};
        int res = solveMthod(n, points);
        System.out.println(res);
    }

    private static int solveMthod(int n, int[][] points) {

        // key是横坐标，value是横坐标上有多少点
        Map<Integer, Integer> map = new HashMap<>();
        addPointToMap(points, map);
        int del = 0;
        for (int i = 0; i < n; i++) {
            int[] point = points[i];
            if (isDeletable(point, map)) {
                removePointsFromMap(point, map);
                del++;
            }
        }
        return n - del;
    }

    private static void removePointsFromMap(int[] point, Map<Integer, Integer> map) {
        for (int j = point[0]; j <= point[1]; j++) {
            map.put(j, map.get(j) - 1);

        }
    }

    private static boolean isDeletable(int[] point, Map<Integer, Integer> map) {
        for (int j = point[0]; j <= point[1]; j++) {
            // map中点出现一次的不可以删除
            if (map.get(j) <= 1) {
                return false;
            }
        }
        return true;
    }


    private static void addPointToMap(int[][] points, Map<Integer, Integer> map) {
        //  举例 points[0] [1,4] 把1到4都加入map
        for (int i = 0; i < points.length; i++) {
            int[] point = points[i];
            for (int j = point[0]; j <= point[1]; j++) {
                map.put(j, map.getOrDefault(j, 0) + 1);
            }

        }

    }
}
